/*
 * @Author: gitee_com_zb
 * @Date: 2024-12-02 15:57:24
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-12-02 15:57:34
 * @FilePath: /algorithm/每日一题5.环形链表II(medium).cpp
 * @Description: 题目链接 https://leetcode.cn/problems/linked-list-cycle-ii?envType=problem-list-v2&envId=two-pointers
 */

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        // 1. 哈希表统计次数
        /* unordered_map<ListNode*, int> hash;
        while(head != nullptr) {
            hash[head]++;
            if(hash[head] > 1) return head;
            head = head->next;
        }
        return nullptr; */
        // 2. 快慢指针
        // 快指针走两步,慢指针走一步,相遇则证明一定有环,
        // 然后让从头开始和慢指针同步走,会在环入口处相遇
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode *ptr = head;
                while (ptr != slow) {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};